Search Results

Documents authored by Abraham, Ittai

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.14
Fever: Optimal Responsive View Synchronisation

Authors: Andrew Lewis-Pye and Ittai Abraham

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
View synchronisation is an important component of many modern Byzantine Fault Tolerant State Machine Replication (SMR) systems in the partial synchrony model. Roughly, the efficiency of view synchronisation is measured as the word complexity and latency required for moving from being synchronised in a view of one correct leader to being synchronised in the view of the next correct leader. The efficiency of view synchronisation has emerged as a major bottleneck in the efficiency of SMR systems as a whole. A key question remained open: Do there exist view synchronisation protocols with asymptotically optimal quadratic worst-case word complexity that also obtain linear complexity and responsiveness when moving between consecutive correct leaders? We answer this question affirmatively with a new view synchronisation protocol for partial synchrony assuming partial initial clock synchronisation, called Fever. If n is the number of processors and t is the largest integer < n/3, then Fever has resilience t, and in all executions with at most 0 ≤ f ≤ t Byzantine parties and network delays of at most δ ≤ Δ after GST (where f and δ are unknown), Fever has worst-case word complexity O(fn+n) and worst-case latency O(Δ f + δ).
Cite as

Andrew Lewis-Pye and Ittai Abraham. Fever: Optimal Responsive View Synchronisation. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lewispye_et_al:LIPIcs.OPODIS.2023.14,
  author =	{Lewis-Pye, Andrew and Abraham, Ittai},
  title =	{{Fever: Optimal Responsive View Synchronisation}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.14},
  URN =		{urn:nbn:de:0030-drops-195041},
  doi =		{10.4230/LIPIcs.OPODIS.2023.14},
  annote =	{Keywords: Distributed Systems, State Machine Replication}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.29
On the Round Complexity of Asynchronous Crusader Agreement

Authors: Ittai Abraham, Naama Ben-David, Gilad Stern, and Sravya Yandamuri

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
We present new lower and upper bounds on the number of communication rounds required for asynchronous Crusader Agreement (CA) and Binding Crusader Agreement (BCA), two primitives that are used for solving binary consensus. We show results for the information theoretic and authenticated settings. In doing so, we present a generic model for proving round complexity lower bounds in the asynchronous setting. In some settings, our attempts to prove lower bounds on round complexity fail. Instead, we show new, tight, rather surprising round complexity upper bounds for Byzantine fault tolerant BCA with and without a PKI setup.
Cite as

Ittai Abraham, Naama Ben-David, Gilad Stern, and Sravya Yandamuri. On the Round Complexity of Asynchronous Crusader Agreement. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2023.29,
  author =	{Abraham, Ittai and Ben-David, Naama and Stern, Gilad and Yandamuri, Sravya},
  title =	{{On the Round Complexity of Asynchronous Crusader Agreement}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{29:1--29:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.29},
  URN =		{urn:nbn:de:0030-drops-195195},
  doi =		{10.4230/LIPIcs.OPODIS.2023.29},
  annote =	{Keywords: lower bounds, asynchronous protocols, round complexity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.1
Colordag: An Incentive-Compatible Blockchain

Authors: Ittai Abraham, Danny Dolev, Ittay Eyal, and Joseph Y. Halpern

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
We present Colordag, a blockchain protocol where following the prescribed strategy is, with high probability, a best response as long as all miners have less than 1/2 of the mining power. We prove the correctness of Colordag even if there is an extremely powerful adversary who knows future actions of the scheduler: specifically, when agents will generate blocks and when messages will arrive. The state-of-the-art protocol, Fruitchain, is an ε-Nash equilibrium as long as all miners have less than 1/2 of the mining power. However, there is a simple deviation that guarantees that deviators are never worse off than they would be by following Fruitchain, and can sometimes do better. Thus, agents are motivated to deviate. Colordag implements a solution concept that we call ε-sure Nash equilibrium and does not suffer from this problem. Because it is an ε-sure Nash equilibrium, Colordag is an ε-Nash equilibrium and with probability 1-ε is a best response.
Cite as

Ittai Abraham, Danny Dolev, Ittay Eyal, and Joseph Y. Halpern. Colordag: An Incentive-Compatible Blockchain. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2023.1,
  author =	{Abraham, Ittai and Dolev, Danny and Eyal, Ittay and Halpern, Joseph Y.},
  title =	{{Colordag: An Incentive-Compatible Blockchain}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.1},
  URN =		{urn:nbn:de:0030-drops-191272},
  doi =		{10.4230/LIPIcs.DISC.2023.1},
  annote =	{Keywords: Game theory, incentives, blockchain}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.16
New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks

Authors: Ittai Abraham and Gilad Stern

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
In 1985, Dolev and Reischuk proved a fundamental communication lower bounds on protocols achieving fault tolerant synchronous broadcast and consensus: any deterministic protocol solving those tasks (even against omission faults) requires at least a quadratic number of messages to be sent by nonfaulty parties. In contrast, many blockchain systems achieve consensus with seemingly linear communication per instance against Byzantine faults. We explore this dissonance in three main ways. First, we extend the Dolev-Reischuk family of lower bounds and prove a new lower bound for Crusader Broadcast protocols. Our lower bound for crusader broadcast requires non-trivial extensions and a much stronger Byzantine adversary with the ability to simulate honest parties. Secondly, we extend our lower bounds to all-but-m Crusader Broadcast, in which up to m parties are allowed to output a different value. Finally, we discuss the ways in which these lower bounds relate to the security of blockchain systems. We show how Eclipse-style attacks in such systems can be viewed as specific instances of the attacks used in our lower bound for Crusader Broadcast. This connection suggests a more systematic way of analyzing and reasoning about Eclipse-style attacks through the lens of the Dolev-Reischuk family of attacks.
Cite as

Ittai Abraham and Gilad Stern. New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2022.16,
  author =	{Abraham, Ittai and Stern, Gilad},
  title =	{{New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.16},
  URN =		{urn:nbn:de:0030-drops-176368},
  doi =		{10.4230/LIPIcs.OPODIS.2022.16},
  annote =	{Keywords: consensus, crusader broadcast, Byzantine fault tolerance, blockchain, synchrony, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.24
Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption

Authors: Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael K. Reiter

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Agreement protocols for partially synchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine faults, but typically at the cost of increased communication complexity. In this work, we present results that use small trusted hardware without worsening communication complexity assuming the adversary controls a fraction of the network that is less than one-half. In particular, we show a version of HotStuff that retains linear communication complexity in each view, leveraging trusted hardware to tolerate a minority of corruptions. Our result uses expander graph techniques to achieve efficient communication in a manner that may be of independent interest.
Cite as

Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael K. Reiter. Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{yandamuri_et_al:LIPIcs.OPODIS.2022.24,
  author =	{Yandamuri, Sravya and Abraham, Ittai and Nayak, Kartik and Reiter, Michael K.},
  title =	{{Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.24},
  URN =		{urn:nbn:de:0030-drops-176448},
  doi =		{10.4230/LIPIcs.OPODIS.2022.24},
  annote =	{Keywords: communication complexity, consensus, trusted hardware}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.38
Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults

Authors: Ittai Abraham, Danny Dolev, Alon Kagan, and Gilad Stern

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Protocols solving authenticated consensus in synchronous networks with Byzantine faults have been widely researched and known to exists if and only if n > 2f for f Byzantine faults. Similarly, protocols solving authenticated consensus in partially synchronous networks are known to exist if n > 3f+2k for f Byzantine faults and k crash faults. In this work we fill a natural gap in our knowledge by presenting MixSync, an authenticated consensus protocol in synchronous networks resilient to f Byzantine faults and k crash faults if n > 2f+k. As a basic building block, we first define and then construct a publicly verifiable crusader agreement protocol with the same resilience. The protocol uses a simple double-send round to guarantee non-equivocation, a technique later used in the MixSync protocol. We then discuss how to construct a state machine replication protocol using these ideas, and how they can be used in general to make such protocols resilient to crash faults. Finally, we prove lower bounds showing that n > 2f+k is optimally resilient for consensus and state machine replication protocols.
Cite as

Ittai Abraham, Danny Dolev, Alon Kagan, and Gilad Stern. Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 38:1-38:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2022.38,
  author =	{Abraham, Ittai and Dolev, Danny and Kagan, Alon and Stern, Gilad},
  title =	{{Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{38:1--38:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.38},
  URN =		{urn:nbn:de:0030-drops-172292},
  doi =		{10.4230/LIPIcs.DISC.2022.38},
  annote =	{Keywords: consensus, state machine replication, mixed faults, synchrony, lower bounds}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.39
Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols

Authors: Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard, and Florian Suri-Payer

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Modern chained BFT SMR protocols have poor liveness under failures as they require multiple consecutive honest leaders to commit a single block. Siesta, our proposed new BFT SMR protocol, is instead able to commit a block that spans multiple non-consecutive honest leaders. Siesta reduces the expected commit latency of HotStuff by a factor of three under failures, and the worst-case latency by a factor of eight.
Cite as

Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard, and Florian Suri-Payer. Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 39:1-39:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2022.39,
  author =	{Abraham, Ittai and Crooks, Natacha and Giridharan, Neil and Howard, Heidi and Suri-Payer, Florian},
  title =	{{Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{39:1--39:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.39},
  URN =		{urn:nbn:de:0030-drops-172305},
  doi =		{10.4230/LIPIcs.DISC.2022.39},
  annote =	{Keywords: Consensus, blockchain, BFT}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.FAB.2022.1
Reflections on the Past, Present and Future of Blockchain Foundations and Applications (Invited Talk)

Authors: Ittai Abraham

Published in: OASIcs, Volume 101, 5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022)

Abstract
We survey some of the amazing progress in Blockchain technology in the last 5 years: from foundations like consensus protocols, execution models, and zero-knowledge proofs, to why these foundations are critical for applications like decentralized finance and web3. The main part of the talk will try to envision the future of Blockchains: how will the "Endgame" look like? What foundations are we still missing? We argue that for Blockchains to thrive and reach Billions of users, we should expect a much more regulated landscape to emerge and discuss some exciting opportunities in reg-crypto and RegDeFi. An example of this direction is our new work on UTT which is a decentralized Ecash system with accountable privacy.
Cite as

Ittai Abraham. Reflections on the Past, Present and Future of Blockchain Foundations and Applications (Invited Talk). In 5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022). Open Access Series in Informatics (OASIcs), Volume 101, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham:OASIcs.FAB.2022.1,
  author =	{Abraham, Ittai},
  title =	{{Reflections on the Past, Present and Future of Blockchain Foundations and Applications}},
  booktitle =	{5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022)},
  pages =	{1:1--1:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-248-8},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{101},
  editor =	{Tucci-Piergiovanni, Sara and Crooks, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.FAB.2022.1},
  URN =		{urn:nbn:de:0030-drops-162686},
  doi =		{10.4230/OASIcs.FAB.2022.1},
  annote =	{Keywords: Blockchain}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.5
Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization

Authors: Ittai Abraham, Ling Ren, and Zhuolun Xiang

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
This paper studies the good-case latency of unauthenticated Byzantine fault-tolerant broadcast, which measures the time it takes for all non-faulty parties to commit given a non-faulty broadcaster. For both asynchrony and synchrony, we show that n ≥ 4f is the tight resilience threshold that separates good-case 2 rounds and 3 rounds. For asynchronous Byzantine reliable broadcast (BRB), we also investigate the bad-case latency for all non-faulty parties to commit when the broadcaster is faulty but some non-faulty party commits. We provide matching upper and lower bounds on the resilience threshold of bad-case latency for BRB protocols with optimal good-case latency of 2 rounds. In particular, we show 2 impossibility results and propose 4 asynchronous BRB protocols.
Cite as

Ittai Abraham, Ling Ren, and Zhuolun Xiang. Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2021.5,
  author =	{Abraham, Ittai and Ren, Ling and Xiang, Zhuolun},
  title =	{{Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.5},
  URN =		{urn:nbn:de:0030-drops-157806},
  doi =		{10.4230/LIPIcs.OPODIS.2021.5},
  annote =	{Keywords: Byzantine broadcast, asynchrony, synchrony, latency, good-case, optimal}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.27
Optimal Good-Case Latency for Rotating Leader Synchronous BFT

Authors: Ittai Abraham, Kartik Nayak, and Nibesh Shrestha

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
This paper explores the good-case latency of synchronous Byzantine Fault Tolerant (BFT) consensus protocols in the rotating leader setting. We first present a lower bound that relates the latency of a broadcast when the sender is honest and the latency of switching to the next sender. We then present a matching upper bound with a latency of 2Δ (Δ is the pessimistic synchronous delay) with an optimistically responsive change to the next sender. The results imply that both our lower and upper bounds are tight. We implement and evaluate our protocol and show that our protocol obtains similar latency compared to state-of-the-art stable-leader protocol Sync HotStuff while allowing optimistically responsive leader rotation.
Cite as

Ittai Abraham, Kartik Nayak, and Nibesh Shrestha. Optimal Good-Case Latency for Rotating Leader Synchronous BFT. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2021.27,
  author =	{Abraham, Ittai and Nayak, Kartik and Shrestha, Nibesh},
  title =	{{Optimal Good-Case Latency for Rotating Leader Synchronous BFT}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.27},
  URN =		{urn:nbn:de:0030-drops-158022},
  doi =		{10.4230/LIPIcs.OPODIS.2021.27},
  annote =	{Keywords: Distributed Computing, Byzantine Fault Tolerance, Synchrony}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.62
Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption

Authors: Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael Reiter

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Small trusted hardware primitives can improve fault tolerance of Byzantine Fault Tolerant (BFT) protocols to one-half faults. However, existing works achieve this at the cost of increased communication complexity. In this work, we explore the design of communication-efficient BFT protocols that can boost fault tolerance to one-half without worsening communication complexity. Our results include a version of HotStuff that retains linear communication complexity in each view and a version of the VABA protocol with quadratic communication, both leveraging trusted hardware to tolerate a minority of corruptions. As a building block, we present communication-efficient provable broadcast, a core broadcast primitive with increased fault tolerance. Our results use expander graphs to achieve efficient communication in a manner that may be of independent interest.
Cite as

Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael Reiter. Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 62:1-62:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{yandamuri_et_al:LIPIcs.DISC.2021.62,
  author =	{Yandamuri, Sravya and Abraham, Ittai and Nayak, Kartik and Reiter, Michael},
  title =	{{Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{62:1--62:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.62},
  URN =		{urn:nbn:de:0030-drops-148647},
  doi =		{10.4230/LIPIcs.DISC.2021.62},
  annote =	{Keywords: communication complexity, consensus, trusted hardware}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.Tokenomics.2020.2
When Nakamoto Meets Nash: Blockchain Breakthrough Through the Lens of Game Theory (Invited Talk)

Authors: Ittai Abraham

Published in: OASIcs, Volume 82, 2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020)

Abstract
We discuss the deep connections between Blockchain Technology, Computer Science and Economics. The talk surveys the ways the Blockchain disruption raises fundamental challenges that have a deep game theoretic nature. We focus on four major open questions: 1) The need for a game theoretic endogenous theory of the utility of Money Systems that can model friction, fairness, and trust. 2) The need to incentivize trust in both consensus and execution. A need for a game theoretic theory of Consensus and analogue to Byzantine Fault Tolerance. A need for a game theoretic framework for scalable validation. 3) The challenge of incentivizing fairness and chain quality. Can we use notions of robust equilibrium to provide better notions of fairness? 4) The open question of how Blockchains can incentivise welfare. The need for a theory of Blockchains as public goods.
Cite as

Ittai Abraham. When Nakamoto Meets Nash: Blockchain Breakthrough Through the Lens of Game Theory (Invited Talk). In 2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020). Open Access Series in Informatics (OASIcs), Volume 82, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abraham:OASIcs.Tokenomics.2020.2,
  author =	{Abraham, Ittai},
  title =	{{When Nakamoto Meets Nash: Blockchain Breakthrough Through the Lens of Game Theory}},
  booktitle =	{2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020)},
  pages =	{2:1--2:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-157-3},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{82},
  editor =	{Anceaume, Emmanuelle and Bisi\`{e}re, Christophe and Bouvard, Matthieu and Bramas, Quentin and Casamatta, Catherine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2020.2},
  URN =		{urn:nbn:de:0030-drops-135248},
  doi =		{10.4230/OASIcs.Tokenomics.2020.2},
  annote =	{Keywords: Game theory, Consensus, Blockchain}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.11
Information Theoretic HotStuff

Authors: Ittai Abraham and Gilad Stern

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
This work presents Information Theoretic HotStuff (IT-HS), a new optimally resilient protocol for solving Byzantine Agreement in partial synchrony with information theoretic security guarantees. In particular, IT-HS does not depend on any PKI or common setup assumptions and is resilient to computationally unbounded adversaries. IT-HS is based on the Primary-Backup view-based paradigm. In IT-HS, in each view, and in each view change, each party sends only a constant number of words to every other party. This yields an O(n²) word and message complexity in each view. In addition, IT-HS requires just O(1) persistent local storage and O(n) transient local storage. Finally, like all Primary-Backup view-based protocols in partial synchrony, after the system becomes synchronous, all nonfaulty parties decide on a value in the first view a nonfaulty leader is chosen. Moreover, like PBFT and HotStuff, IT-HS is optimistically responsive: with a nonfaulty leader, parties decide as quickly as the network allows them to do so, without regard for the known upper bound on network delay. Our work improves in multiple dimensions upon the information theoretic version of PBFT presented by Miguel Castro, and can be seen as an information theoretic variant of the HotStuff paradigm.
Cite as

Ittai Abraham and Gilad Stern. Information Theoretic HotStuff. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2020.11,
  author =	{Abraham, Ittai and Stern, Gilad},
  title =	{{Information Theoretic HotStuff}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.11},
  URN =		{urn:nbn:de:0030-drops-134969},
  doi =		{10.4230/LIPIcs.OPODIS.2020.11},
  annote =	{Keywords: byzantine agreement, partial synchrony, bounded space}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.47
Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-Case Latency

Authors: Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
This paper investigates the problem good-case latency of Byzantine agreement, broadcast and state machine replication in the synchronous authenticated setting. The good-case latency measure captures the time it takes to reach agreement when all non-faulty parties have the same input (or in BB/SMR when the sender/leader is non-faulty) and all messages arrive instantaneously. Previous result implies a lower bound showing that any Byzantine agreement or broadcast protocol tolerating more than n/3 faults must have a good-case latency of at least Δ. Our first result is a matching tight upper bound for a family of protocols we call 1Δ. We propose a protocol 1Δ-BA that solves Byzantine agreement in the synchronous and authenticated setting with optimal good-case latency of Δ and optimal resilience f < n/2. We then extend our protocol and present 1Δ-BB and 1Δ-SMR for Byzantine fault tolerant broadcast and state machine replication, respectively, in the same setting and with the same optimal good-case latency of Δ and f < n/2 fault tolerance.
Cite as

Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-Case Latency. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 47:1-47:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2020.47,
  author =	{Abraham, Ittai and Nayak, Kartik and Ren, Ling and Xiang, Zhuolun},
  title =	{{Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-Case Latency}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{47:1--47:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.47},
  URN =		{urn:nbn:de:0030-drops-131259},
  doi =		{10.4230/LIPIcs.DISC.2020.47},
  annote =	{Keywords: Byzantine broadcast, synchrony, latency, state machine replication}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.25
Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus

Authors: Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time. Another chal- lenge is the lack of incentives at certain steps of the protocol, raising concerns for transaction withholding, selfish mining, etc. To address these challenges, we propose Solida, a decentralized blockchain protocol based on reconfigurable Byzantine consensus augmented by proof-of-work. Solida improves on Bitcoin in confirmation time, and provides safety and liveness assuming the adversary control less than (roughly) one-third of the total mining power.
Cite as

Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman. Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2017.25,
  author =	{Abraham, Ittai and Malkhi, Dahlia and Nayak, Kartik and Ren, Ling and Spiegelman, Alexander},
  title =	{{Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.25},
  URN =		{urn:nbn:de:0030-drops-86409},
  doi =		{10.4230/LIPIcs.OPODIS.2017.25},
  annote =	{Keywords: Cryptocurrency, Blockchain, Byzantine fault tolerance, Reconfiguration}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.41
Brief Announcement: Practical Synchronous Byzantine Consensus

Authors: Ittai Abraham, Srinivas Devadas, Kartik Nayak, and Ling Ren

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
This paper presents new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. The PBFT state machine replication protocol tolerates f Byzantine faults in an asynchronous setting using n = 3f + 1 replicas. We improve the Byzantine fault tolerance to n = 2f + 1 by utilizing the synchrony assumption. Our protocol also solves synchronous authenticated Byzantine agreement in fewer expected rounds than the best existing solution (Katz and Koo, 2006).
Cite as

Ittai Abraham, Srinivas Devadas, Kartik Nayak, and Ling Ren. Brief Announcement: Practical Synchronous Byzantine Consensus. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 41:1-41:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2017.41,
  author =	{Abraham, Ittai and Devadas, Srinivas and Nayak, Kartik and Ren, Ling},
  title =	{{Brief Announcement: Practical Synchronous Byzantine Consensus}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{41:1--41:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.41},
  URN =		{urn:nbn:de:0030-drops-79703},
  doi =		{10.4230/LIPIcs.DISC.2017.41},
  annote =	{Keywords: consensus, agreement, Byzantine fault tolerance, replication, synchrony}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.20
Approximate Nearest Neighbor Search in Metrics of Planar Graphs

Authors: Ittai Abraham, Shiri Chechik, Robert Krauthgamer, and Udi Wieder

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
We investigate the problem of approximate Nearest-Neighbor Search (NNS) in graphical metrics: The task is to preprocess an edge-weighted graph G=(V,E) on m vertices and a small "dataset" D \subset V of size n << m, so that given a query point q \in V, one can quickly approximate dist(q,D) (the distance from q to its closest vertex in D) and find a vertex a \in D within this approximated distance. We assume the query algorithm has access to a distance oracle, that quickly evaluates the exact distance between any pair of vertices. For planar graphs G with maximum degree Delta, we show how to efficiently construct a compact data structure -- of size ~O(n(Delta+1/epsilon)) -- that answers (1+epsilon)-NNS queries in time ~O(Delta+1/epsilon). Thus, as far as NNS applications are concerned, metrics derived from bounded-degree planar graphs behave as low-dimensional metrics, even though planar metrics do not necessarily have a low doubling dimension, nor can they be embedded with low distortion into l_2. We complement our algorithmic result by lower bounds showing that the access to an exact distance oracle (rather than an approximate one) and the dependency on Delta (in query time) are both essential.
Cite as

Ittai Abraham, Shiri Chechik, Robert Krauthgamer, and Udi Wieder. Approximate Nearest Neighbor Search in Metrics of Planar Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 20-42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.APPROX-RANDOM.2015.20,
  author =	{Abraham, Ittai and Chechik, Shiri and Krauthgamer, Robert and Wieder, Udi},
  title =	{{Approximate Nearest Neighbor Search in Metrics of Planar Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{20--42},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.20},
  URN =		{urn:nbn:de:0030-drops-52923},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.20},
  annote =	{Keywords: Data Structures, Nearest Neighbor Search, Planar Graphs, Planar Metrics, Planar Separator}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.1
Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier

Authors: Ittai Abraham, Shiri Chechik, and Kunal Talwar

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
A fully dynamic approximate distance oracle is a distance reporting data structure that supports dynamic insert edge and delete edge operations. In this paper we break a longstanding barrier in the design of fully dynamic all-pairs approximate distance oracles. All previous results for this model incurred an amortized cost of at least Omega(n) per operation. We present the first construction that provides constant stretch and o(m) amortized update time. For graphs that are not too dense (where |E| = O(|V|^{2-delta}) for some delta>0 we break the O(n) barrier and provide the first construction with constant stretch and o(n) amortized cost.
Cite as

Ittai Abraham, Shiri Chechik, and Kunal Talwar. Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.APPROX-RANDOM.2014.1,
  author =	{Abraham, Ittai and Chechik, Shiri and Talwar, Kunal},
  title =	{{Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.1},
  URN =		{urn:nbn:de:0030-drops-46857},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.1},
  annote =	{Keywords: Shortest Paths, Dynamic Algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact